When two or more devices share a communication medium, a medium-access control (MAC) protocol is required to deal with the possibility of collisions. For example, the traditional Ethernet MAC uses carrier sense multiple access with collision detection (CSMA/CD), as described in R. M. Metcalfe et al., “Ethernet: Distributed Packet Switching for Local Computer Networks,” Communications of the ACM, vol. 19, no. 7, pp. 395-404, July 1976. However, CSMA/CD is not universally applicable.
Consider by way of example the architecture of a broadband access network. Such a network typically comprises a single head-end device, located at the service-provider head-end facility, connected over a point-to-multipoint network to many devices located at or proximate the subscriber locations. More specific examples of such networks include DOCSIS-compliant cable-modem networks, described in “Data-over-cable service interface specifications radio frequency interface specification,” Tech. Rep. SP-RFIv2.0-I01-011231,” Cable Television Laboratories, Inc., December 2001, and various types of passive optical networks (PONs), such as Ethernet PONs (EPONs) as described in G. Kramer et al. “Ethernet Passive Optical Network (EPON): Building a Next-Generation Optical Access Network,” IEEE Communications, pp. 66-73, February 2002. The head-end device connects the access network to some other external network, typically the Internet. The subscriber device connects the access network to the subscriber network, which may be as simple as a point-to-point Ethernet connection to a home personal computer (PC).
One can visualize an access network as a tree topology in which the head-end device broadcasts the downstream traffic to all subscriber devices, and each subscriber device “picks off” the traffic directed to it based on some protocol-specific addressing. In the upstream direction the medium is shared and hence requires a MAC protocol. If two subscriber devices transmitted at the same time, the signal would propagate upstream from two leaves of the tree and a collision would occur in either the access network or the head-end device.
In contrast to a traditional enterprise-scale Ethernet, an access network has endpoints that do not necessarily hear each other's transmissions, so CSMA/CD is not a viable option. Furthermore, the end-to-end propagation delays in an access network are too large for CSMA/CD to be practical. Instead, many access networks use a SMAP, in which the head-end device periodically informs the subscriber devices when it is their turn to transmit. If the schedule is correctly constructed, if no devices misbehave, and if time is properly synchronized among the head-end and subscriber devices, then collisions do not occur.
To construct the schedule, the head-end device runs a scheduling algorithm, which can be static (each subscriber device is given a fixed, regular fraction of the upstream medium, regardless of load), or dynamic (each device is given a timeslot allocation that is related to its current load and possibly some quality-of-service (QoS) parameters). SMAPs that support dynamic bandwidth allocation also provide a mechanism whereby each subscriber device can periodically report its load to the head-end device.
Activities such as scheduling, granting, time synchronization, and reporting are the basic components of a typical SMAP. The granting and reporting mechanisms are precisely defined by the protocol to ensure interoperability among the devices in the network. The scheduling algorithm, however, is typically left to the implementor, with the single requirement that the resulting grants do not cause collisions. Grants may also be required to meet any QoS requirements that the SMAP imposes.
The functions of any computer system (SMAP or otherwise) can be implemented in a number of different ways. For example, some functionality can be implemented in a general-purpose programming language such as C and run on a general-purpose processor; some functionality can be implemented in an assembly or C-like language and run on a network processor; some functionality can be implemented in a hardware-description language such as Verilog or VHDL and run in a programmable logic device; and some functionality can be implemented directly in an application-specific integrated circuit (ASIC).
Thus, it is possible to implement the basic components of a typical SMAP using a combination of software and hardware. Determining which portions of the SMAP are implemented in software and which are implemented in hardware is referred to herein as “software-hardware partitioning” of the SMAP. In this context, the term “software” is intended to refer to code executable on a general-purpose processor, while the term “hardware” refers to all other ways of implementing a system, including use of one or more network processors, programmable logic devices or ASICs.
The determination of the optimal software-hardware partitioning for a given SMAP is a difficult problem that has not been adequately addressed in conventional practice.
Accordingly, what is needed is a software-hardware partitioning technique that is applicable to a wide variety of SMAPs. The technique should be simple and efficient, and should allow all complex, application-dependent code to be implemented in software.